Search Results

Documents authored by Chen, Ke

Found 2 Possible Name Variants:

Chen, Ke

Document
DOI: 10.4230/LIPIcs.WABI.2022.22
Locality-Sensitive Bucketing Functions for the Edit Distance

Authors: Ke Chen and Mingfu Shao

Published in: LIPIcs, Volume 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)

Abstract
Many bioinformatics applications involve bucketing a set of sequences where each sequence is allowed to be assigned into multiple buckets. To achieve both high sensitivity and precision, bucketing methods are desired to assign similar sequences into the same bucket while assigning dissimilar sequences into distinct buckets. Existing k-mer-based bucketing methods have been efficient in processing sequencing data with low error rate, but encounter much reduced sensitivity on data with high error rate. Locality-sensitive hashing (LSH) schemes are able to mitigate this issue through tolerating the edits in similar sequences, but state-of-the-art methods still have large gaps. Here we generalize the LSH function by allowing it to hash one sequence into multiple buckets. Formally, a bucketing function, which maps a sequence (of fixed length) into a subset of buckets, is defined to be (d₁, d₂)-sensitive if any two sequences within an edit distance of d₁ are mapped into at least one shared bucket, and any two sequences with distance at least d₂ are mapped into disjoint subsets of buckets. We construct locality-sensitive bucketing (LSB) functions with a variety of values of (d₁,d₂) and analyze their efficiency with respect to the total number of buckets needed as well as the number of buckets that a specific sequence is mapped to. We also prove lower bounds of these two parameters in different settings and show that some of our constructed LSB functions are optimal. These results provide theoretical foundations for their practical use in analyzing sequences with high error rate while also providing insights for the hardness of designing ungapped LSH functions.
Cite as

Ke Chen and Mingfu Shao. Locality-Sensitive Bucketing Functions for the Edit Distance. In 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 242, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.WABI.2022.22,
  author =	{Chen, Ke and Shao, Mingfu},
  title =	{{Locality-Sensitive Bucketing Functions for the Edit Distance}},
  booktitle =	{22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-243-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{242},
  editor =	{Boucher, Christina and Rahmann, Sven},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.22},
  URN =		{urn:nbn:de:0030-drops-170563},
  doi =		{10.4230/LIPIcs.WABI.2022.22},
  annote =	{Keywords: Locality-sensitive hashing, locality-sensitive bucketing, long reads, embedding}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.42
Multiparty Selection

Authors: Ke Chen and Adrian Dumitrescu

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Given a sequence A of n numbers and an integer (target) parameter 1 ≤ i ≤ n, the (exact) selection problem is that of finding the i-th smallest element in A. An element is said to be (i,j)-mediocre if it is neither among the top i nor among the bottom j elements of S. The approximate selection problem is that of finding an (i,j)-mediocre element for some given i,j; as such, this variant allows the algorithm to return any element in a prescribed range. In the first part, we revisit the selection problem in the two-party model introduced by Andrew Yao (1979) and then extend our study of exact selection to the multiparty model. In the second part, we deduce some communication complexity benefits that arise in approximate selection. In particular, we present a deterministic protocol for finding an approximate median among k players.
Cite as

Ke Chen and Adrian Dumitrescu. Multiparty Selection. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2020.42,
  author =	{Chen, Ke and Dumitrescu, Adrian},
  title =	{{Multiparty Selection}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{42:1--42:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.42},
  URN =		{urn:nbn:de:0030-drops-133867},
  doi =		{10.4230/LIPIcs.ISAAC.2020.42},
  annote =	{Keywords: approximate selection, mediocre element, comparison algorithm, i-th order statistic, tournaments, quantiles, communication complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.56
On the Stretch Factor of Polygonal Chains

Authors: Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, and Csaba D. Tóth

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
Let P=(p_1, p_2, ..., p_n) be a polygonal chain. The stretch factor of P is the ratio between the total length of P and the distance of its endpoints, sum_{i = 1}^{n-1} |p_i p_{i+1}|/|p_1 p_n|. For a parameter c >= 1, we call P a c-chain if |p_ip_j|+|p_jp_k| <= c|p_ip_k|, for every triple (i,j,k), 1 <= i<j<k <= n. The stretch factor is a global property: it measures how close P is to a straight line, and it involves all the vertices of P; being a c-chain, on the other hand, is a fingerprint-property: it only depends on subsets of O(1) vertices of the chain. We investigate how the c-chain property influences the stretch factor in the plane: (i) we show that for every epsilon > 0, there is a noncrossing c-chain that has stretch factor Omega(n^{1/2-epsilon}), for sufficiently large constant c=c(epsilon); (ii) on the other hand, the stretch factor of a c-chain P is O(n^{1/2}), for every constant c >= 1, regardless of whether P is crossing or noncrossing; and (iii) we give a randomized algorithm that can determine, for a polygonal chain P in R^2 with n vertices, the minimum c >= 1 for which P is a c-chain in O(n^{2.5} polylog n) expected time and O(n log n) space.
Cite as

Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, and Csaba D. Tóth. On the Stretch Factor of Polygonal Chains. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.MFCS.2019.56,
  author =	{Chen, Ke and Dumitrescu, Adrian and Mulzer, Wolfgang and T\'{o}th, Csaba D.},
  title =	{{On the Stretch Factor of Polygonal Chains}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.56},
  URN =		{urn:nbn:de:0030-drops-110005},
  doi =		{10.4230/LIPIcs.MFCS.2019.56},
  annote =	{Keywords: polygonal chain, vertex dilation, Koch curve, recursive construction}
}

Chen, Ken

Document
DOI: 10.4230/DagSemProc.04411.21
Some lessons from an experience with active video flow regulation

Authors: Ken Chen and Rim Hammi

Published in: Dagstuhl Seminar Proceedings, Volume 4411, Service Management and Self-Organization in IP-based Networks (2005)

Abstract
People are paying more and more attention to network infrastructures which are capable of dynamic code deployment and reconfiguration, in order to deal with the increase of network complexity both on scale and on heterogeneity. The concept of "active network" has been one of the pioneer ideas. As a starting point, we present an experience we got through the design and implementation of an active network technology based mechanism for video flow regulation. This mechanism makes use of several typical active networking features to perform real-time video flows analysis and provide consequently responsive feedback control to video codec. The main goal here is to adapt quickly the video stream bitrate to the current available bandwidth. From the end-user's view point, the effect of adaptation is to spread the bitrate reduction (relatively) uniformly to all the stream, avoiding in this way abrupt image deterioration (mosaics) due to packet loss. Tests show visible improvements obtained by our mechanism vs the classical RTCP-based control scheme. This work has been jointly done with Rim Hammi. We then discuss some extensions of our mechanism, which is in fact a generic network observer and decision maker. A more fundamental issue that we identified from this experience is related to the setting of the criteria for code acceptation. This is in fact a rather generic problem, and one can address it in various way. For instance, one can decide to accept a code based on some authentication rule. We are particularly interested by the issue of resources consummation. Indeed, as an example, the network observer module we designed can be configured to get a more or less fine time granularity, and consequently consume more or less CPU. So, one question is how to prevent abusive (either erroneous or malicious) resource consummation. There is few tentative which try to deal with the resource requirement (bandwidth, CPU, memory, etc.) of a code. The problem is rather complex and hard. It should at least include the monitoring of resource consummation. It requires also a kind of virtual resource model for coding purpose. This issue is, in our opinion, very important. Indeed, we do need a control framework to guarantee not only the correct functionality but also the adequate resource consummation of various codes, in order to be able to deal with future's flexible and/or autonomic networks in a secure and trustable way. Our current research effort on this issue is carried on within the french RNRT/Amarillo project.
Cite as

Ken Chen and Rim Hammi. Some lessons from an experience with active video flow regulation. In Service Management and Self-Organization in IP-based Networks. Dagstuhl Seminar Proceedings, Volume 4411, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:DagSemProc.04411.21,
  author =	{Chen, Ken and Hammi, Rim},
  title =	{{Some lessons from an experience with active video flow regulation}},
  booktitle =	{Service Management and Self-Organization in IP-based Networks},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4411},
  editor =	{Matthias Bossardt and Georg Carle and D. Hutchison and Hermann de Meer and Bernhard Plattner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04411.21},
  URN =		{urn:nbn:de:0030-drops-859},
  doi =		{10.4230/DagSemProc.04411.21},
  annote =	{Keywords: active network , video streaming , resource control , responsive control}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact